1. Field of the Invention
The present invention relates to computer aided design ("CAD") systems and, more particularly, to the concurrent editing of raster and vector entities in a single image layer, and the selective conversion and erasure of raster entities.
2. The Prior Art
The present invention comprises an improved image editor of the type used for computer aided design and drafting ("CADD"), more commonly known as computer aided design ("CAD"). One type of image editor, a raster editor, is oftentimes used to make changes to a preexisting hardcopy drawing that is scanned into a computer as a digital image. Due to their simplicity of engineering, document scanners that digitize hardcopy drawings are typically rasterizing devices and, thus, most preexisting drawings are raster images that must be modified with a raster editor. Raster images are made up of a matrix of individually addressable pixels, which are ultimately represented inside of a computer as bit-maps. These digitized images include geometric shapes, or entities, such as polygons, that can be manipulated by the user of the raster editor.
An image editor will typically edit digitized entities that are represented and stored in a file in only one of two different formats, known as raster and vector. For example, one entity of a raster image may be a circle. A circle is described in raster format by the set of individual pixels around the circumference of the circle, where each pixel is identified by an x-y coordinate. The same circle described in vector format is stored in memory as the tuple comprising the center of the circle (an x-y coordinate) and the radius of the circle.
Vector editors are typically used to create and edit digital images where no preexisting hardcopy drawing must be modified since it is well known that manipulations on vector entities, such as "scale" and "move", will be far less computationally intensive than manipulations on the same entity in a raster format. Furthermore, a clear advantage in memory usage results when digitized entities are stored in vector format since the individual pixels of an entity do not have to be stored.
For some time now, a need has existed for converting raster entities into vector entities to take advantage of the more powerful and less time-consuming editing operations that are commonly associated with vector editors. Pferd, et al., (U.S. Pat. No. 4,307,377), was an early attempt at converting raster images into vector images. The patent discloses a vector coding technique to extract vector information in real-time from raster-type data scanned line-by-line. As part of a pre-processing function the technique fills in line gaps which are found in the graphics information. After pre-processing, a pair of adjacent scan lines are monitored for indications of edge-to-edge transitions and they are compared in position and slope for continuations of line lengths. Line vectors are thus created and stored as two sets of rectangular coordinates and a number representing a line thickness. Pferd, et al., does not address complex entity conversion such as the conversion of arcs and polylines. Nor does the patent disclose conversion of overlapping entities or entities that have been "recognized" according to a predetermined entity template.
More recently, patents to McCann, et al. and Lien disclose other means for converting raster data into vector data. The system shown in McCann, et al. (U.S. Pat. No. 4,777,651) converts raster scan data into a list of vectors which can be edited, displayed and stored. It is therein suggested that the database of vectors can be used for syntactic pattern recognition such as identifying arcs, characters or other features. The rasterized bit-map which is input to the system is segmented into a series of windows, and neighborhood logic elements perform transformation operations such as growing, smoothing and thinning. Line segments are "chain coded" in lists and then converted to the final output vectors.
Lien (U.S. Pat. No. 4,817,187) shows a vectorizer for hand drawn technical drawings that have been digitized. The vectors are created by serially scanning "run length" data. Run length data is accumulated into records defining a "basic shape", such as an arc vector, line vector or filled shape. An object, as defined by the Lien Patent, comprises a number of connected basic shapes which are referred to as either "trapezoids" comprising four corner points or "blobs", defined as non-trapezoidal polygons. According to the Lien disclosure, the technique identifies arc vectors, line vectors and filled shapes.
While the above-identified patents disclose various techniques for converting a raster image into a vector image, none of them address the issues of "selective" conversion and "selective" erasure. If the goal is to make modifications to existing raster images, it would be a more efficient and accurate process to only choose selected entities of the image to vectorize. In most applications, the majority of the raster image seldom needs to be modified, so in most cases it is not wise to expend time converting an entire raster image. In addition, one would expect that where entities overlap one another as is often the case, there would be fewer problems associated with misidentifying pieces of other entities as belonging to a selected entity if the process of entity recognition was guided by some predetermined geometric shape. It would also be a significant advantage if, after a selected entity was recognized and converted, the selected raster entity could be erased from among other overlapping raster entities such that the integrity of the other raster entities was maintained.
Other known systems in the prior art allow raster and vector entities to be edited with a single computer program. However, these systems treat raster and vector entities as distinct image layers and, as a result, entirely different edit operations must be used to manipulate the raster and vector entities. Thus, in such systems the user must be consciously aware of the internal representation of the entity being edited so that the appropriate raster or vector edit operations can be selected.
Consequently, a need exists for an image editing system which is characterized by entity directed vectorization, overlapping entity vectorization and erasure, and editing of coexisting raster and vector entities in the same image layer.